SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Stack machine</title>

</head>

Stack machine

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For stack machines in automata theory, see <a href="Pushdown_automaton" title="Pushdown automaton">Pushdown automaton</a>.</div>

In <a href="Computer_science" title="Computer science">computer science</a>, <a href="Computer_engineering" title="Computer engineering">computer engineering</a> and <a href="Programming_language_implementation" title="Programming language implementation">programming language implementations</a>, a stack machine is a <a href="Computer_processor" class="mw-redirect" title="Computer processor">computer processor</a> or a <a href="Virtual_machine#Process_virtual_machines" title="Virtual machine">process virtual machine</a> in which the primary interaction is moving short-lived temporary values to and from a push down <a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">stack</a>. In the case of a hardware processor, a <a href="Hardware_stack" class="mw-redirect" title="Hardware stack">hardware stack</a> is used. The use of a stack significantly reduces the required number of <a href="Processor_register" title="Processor register">processor registers</a>. Stack machines extend <a href="Push-down_automata" class="mw-redirect" title="Push-down automata">push-down automata</a> with additional load/store operations or multiple stacks and hence are <a href="Turing-complete" class="mw-redirect" title="Turing-complete">Turing-complete</a>.

<div class="mw-heading mw-heading2"><h2 id="Design">Design</h2></div>

Most or all stack machine instructions assume that operands will be from the stack, and results placed in the stack. The stack easily holds more than two inputs or more than one result, so a rich set of operations can be computed. In stack machine code (sometimes called <a href="P-code" class="mw-redirect" title="P-code">p-code</a>), instructions will frequently have only an <a href="Opcode" title="Opcode">opcode</a> commanding an operation, with no additional fields identifying a constant, register or memory cell, known as a zero address format.<a href="#cite_note-Beard_1997-1">[1]</a> A computer that operates in such a way that the majority of its instructions do not include explicit addresses is said to utilize zero-address instructions.<a href="#cite_note-2">[2]</a> This greatly simplifies instruction decoding. Branches, load immediates, and load/store instructions require an argument field, but stack machines often arrange that the frequent cases of these still fit together with the opcode into a compact group of <a href="Bit" title="Bit">bits</a>. The selection of operands from prior results is done implicitly by ordering the instructions. Some stack machine instruction sets are intended for interpretive execution of a virtual machine, rather than driving hardware directly.

Integer constant operands are pushed by <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Push</code> or <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Load Immediate</code> instructions. Memory is often accessed by separate <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Load</code> or <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Store</code> instructions containing a memory address or calculating the address from values in the stack. All practical stack machines have variants of the load–store opcodes for accessing <a href="Local_variable" title="Local variable">local variables</a> and <a href="Formal_parameter" class="mw-redirect" title="Formal parameter">formal parameters</a> without explicit address calculations. This can be by offsets from the current top-of-stack address, or by offsets from a stable frame-base register.

The <a href="Instruction_set" class="mw-redirect" title="Instruction set">instruction set</a> carries out most ALU actions with postfix (<a href="Reverse_Polish_notation" title="Reverse Polish notation">reverse Polish notation</a>) operations that work only on the expression stack, not on data registers or main memory cells. This can be very convenient for executing high-level languages because most arithmetic expressions can be easily translated into postfix notation.

For example, consider the expression A*(B-C)+(D+E), written in reverse Polish notation as A B C - * D E + +. Compiling and running this on a simple imaginary stack machine would take the form:

<pre> # stack contents (leftmost = top = most recent):

push A # A

push B # B A

push C # C B A

subtract # B-C A

multiply # A*(B-C)

push D # D A*(B-C)

push E # E D A*(B-C)

add # D+E A*(B-C)

add # A*(B-C)+(D+E)

</pre>

The arithmetic operations 'subtract', 'multiply', and 'add' act on the two topmost operands of the stack. The computer takes both operands from the topmost (most recent) values of the stack. The computer replaces those two values with the calculated difference, sum, or product. In other words the instruction's operands are "popped" off the stack, and its result(s) are then "pushed" back onto the stack, ready for the next instruction.

Stack machines may have their expression stack and their <a href="Call_stack" title="Call stack">call-return stack</a> separated or as one integrated structure. If they are separated, the instructions of the stack machine can be <a href="Instruction_pipelining" title="Instruction pipelining">pipelined</a> with fewer interactions and less design complexity, so it will usually run faster.

Optimisation of compiled stack code is quite possible. Back-end optimisation of compiler output has been demonstrated to significantly improve code,<a href="#cite_note-Koopman_1994-3">[3]</a><a href="#cite_note-Bailey_2000-4">[4]</a> and potentially performance, whilst global optimisation within the compiler itself achieves further gains.<a href="#cite_note-Shannon-Bailey_2006-5">[5]</a>

<div class="mw-heading mw-heading3"><h3 id="Stack_storage">Stack storage</h3></div>

Some stack machines have a stack of limited size, implemented as a register file. The ALU will access this with an index. A large register file uses a lot of transistors and hence this method is only suitable for small systems. A few machines have both an expression stack in memory and a separate register stack. In this case, software, or an interrupt may move data between them. Some machines have a stack of unlimited size, implemented as an array in RAM, which is cached by some number of "top of stack" address registers to reduce memory access. Except for explicit "load from memory" instructions, the order of operand usage is identical with the order of the operands in the data stack, so excellent prefetching can be accomplished easily.

Consider <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">X+1</code>. It compiles to <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Load X</code>; <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Load 1</code>; <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Add</code>. With a stack stored completely in RAM, this does implicit writes and reads of the in-memory stack:

<ul><li>Load X, push to memory</li>

<li>Load 1, push to memory</li>

<li>Pop 2 values from memory, add, and push result to memory</li></ul>

for a total of 5 data cache references.

The next step up from this is a stack machine or interpreter with a single top-of-stack register. The above code then does:

<ul><li>Load X into empty TOS register (if hardware machine) or Push TOS register to memory, Load X into TOS register (if interpreter)</li>

<li>Push TOS register to memory, Load 1 into TOS register</li>

<li>Pop left operand from memory, add to TOS register and leave it there</li></ul>

for a total of 3 data cache references, worst-case. Generally, interpreters don't track emptiness, because they don't have to—anything below the stack pointer is a non-empty value, and the TOS cache register is always kept hot. Typical Java interpreters do not buffer the top-of-stack this way, however, because the program and stack have a mix of short and wide data values.

If the hardwired stack machine has 2 or more top-stack registers, or a register file, then all memory access is avoided in this example and there is only 1 data cache cycle.

<div class="mw-heading mw-heading2"><h2 id="History_and_implementations">History and implementations</h2></div>

Description of such a method requiring only two values at a time to be held in registers, with a limited set of pre-defined operands that were able to be extended by definition of further operands, functions and subroutines, was first provided at conference by <a href="Robert_S._Barton" title="Robert S. Barton">Robert S. Barton</a> in 1961.<a href="#cite_note-Barton_1961-6">[6]</a><a href="#cite_note-Barton_1987-7">[7]</a>

<div class="mw-heading mw-heading3"><h3 id="Commercial_stack_machines">Commercial stack machines</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="High-level_language_computer_architecture" title="High-level language computer architecture">High-level language computer architecture</a></div>

Examples of stack instruction sets directly executed in hardware include

<ul><li>the <a href="Z4_(computer)" title="Z4 (computer)">Z4</a> (1945) computer by <a href="Konrad_Zuse" title="Konrad Zuse">Konrad Zuse</a> had a 2-level stack.<a href="#cite_note-Blaauw-Brooks_1997-8">[8]</a><a href="#cite_note-LaForest_2007-9">[9]</a></li>

<li>the <a href="Burroughs_large_systems" class="mw-redirect" title="Burroughs large systems">Burroughs large systems</a> architecture (since 1961)</li>

<li>the <a href="English_Electric_KDF9" title="English Electric KDF9">English Electric KDF9</a> machine. First delivered in 1964, the KDF9 had a 19-level deep pushdown stack of arithmetic registers, and a 17-level deep stack for subroutine return addresses</li>

<li>the <a href="Collins_Radio" class="mw-redirect" title="Collins Radio">Collins Radio</a> Collins Adaptive Processing System minicomputer (CAPS, since 1969) and <a href="Rockwell_Collins" title="Rockwell Collins">Rockwell Collins</a> Advanced Architecture Microprocessor (AAMP, since 1981).<a href="#cite_note-Greve-Wilding_1998-10">[10]</a></li>

<li>the <a href="Xerox_Star#Hardware" title="Xerox Star">Xerox Dandelion</a>, introduced 27 April 1981, and the <a href="Xerox_Daybreak" title="Xerox Daybreak">Xerox Daybreak</a> utilized a stack machine architecture to save memory.<a href="#cite_note-Xerox_Mesa-11">[11]</a><a href="#cite_note-DigiBarn_Star-12">[12]</a></li>

<li>the <a href="UCSD_Pascal" title="UCSD Pascal">UCSD Pascal</a> p-machine (as the <a href="Pascal_MicroEngine" title="Pascal MicroEngine">Pascal MicroEngine</a> and many others) supported a complete student programming environment on early 8-bit microprocessors with poor instruction sets and little RAM, by compiling to a virtual stack machine.</li>

<li><a href="Manchester_computers" title="Manchester computers">MU5</a> and <a href="ICL_2900_Series" title="ICL 2900 Series">ICL 2900 Series</a>. Hybrid stack and accumulator machines. The accumulator register buffered the memory stack's top data value. Variants of load and store opcodes controlled when that register was spilled to the memory stack or reloaded from there.</li>

<li><a href="HP_3000" title="HP 3000">HP 3000</a> (Classic, not PA-RISC)</li>

<li><a href="HP_9000" title="HP 9000">HP 9000</a> systems based on the <a href="HP_FOCUS" title="HP FOCUS">HP FOCUS</a> microprocessor.<a href="#cite_note-13">[13]</a></li>

<li><a href="Tandem_Computers" title="Tandem Computers">Tandem Computers</a> T/16. Like HP 3000, except that compilers, not microcode, controlled when the register stack spilled to the memory stack or was refilled from the memory stack.</li>

<li>the <a href="Atmel" title="Atmel">Atmel</a> MARC4 <a href="Microcontroller" title="Microcontroller">microcontroller</a><a href="#cite_note-MARC4-14">[14]</a></li>

<li>Several "Forth chips"<a href="#cite_note-Colorforth-15">[15]</a> such as the RTX2000, the <a href="RTX2010" class="mw-redirect" title="RTX2010">RTX2010</a>, the F21<a href="#cite_note-UT_F21-16">[16]</a> and the <a href="Ignite_(microprocessor)" title="Ignite (microprocessor)">PSC1000</a><a href="#cite_note-ForthHub_2017-17">[17]</a><a href="#cite_note-Java_1999-18">[18]</a></li>

<li>The <a href="Setun" title="Setun">Setun</a> <a href="Ternary_computer" title="Ternary computer">Ternary computer</a> performed <a href="Balanced_ternary" title="Balanced ternary">balanced ternary</a> using a stack.</li>

<li>Patriot Scientific's <a href="Ignite_(microprocessor)" title="Ignite (microprocessor)">Ignite</a> stack machine designed by <a href="Charles_H._Moore" title="Charles H. Moore">Charles H. Moore</a> holds a leading functional density benchmark.</li>

<li><a href="Saab_Ericsson_Space" class="mw-redirect" title="Saab Ericsson Space">Saab Ericsson Space</a> Thor <a href="Radiation_hardened" class="mw-redirect" title="Radiation hardened">radiation hardened</a> microprocessor<a href="#cite_note-Lundqvist_1995-19">[19]</a></li>

<li><a href="Inmos" title="Inmos">Inmos</a> <a href="Transputer" title="Transputer">transputers</a>.</li>

<li><a href="ZPU_(microprocessor)" class="mw-redirect" title="ZPU (microprocessor)">ZPU</a> A physically-small CPU designed to supervise <a href="FPGA" class="mw-redirect" title="FPGA">FPGA</a> systems.<a href="#cite_note-ZPU-20">[20]</a></li>

<li>Some technical handheld calculators use reverse Polish notation in their keyboard interface, instead of having parenthesis keys. This is a form of stack machine. The Plus key relies on its two operands already being at the correct topmost positions of the user-visible stack.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Virtual_stack_machines">Virtual stack machines</h3></div>

Examples of <a href="Virtual_machine" title="Virtual machine">virtual</a> stack machines interpreted in software:

<ul><li>the <a href="Whetstone_(benchmark)" title="Whetstone (benchmark)">Whetstone</a> <a href="ALGOL_60" title="ALGOL 60">ALGOL 60</a> interpretive code,<a href="#cite_note-Randell-Russell_1964-21">[21]</a> on which some features of the Burroughs B6500 were based</li>

<li>the <a href="UCSD_Pascal" title="UCSD Pascal">UCSD Pascal</a> p-machine; which closely resembled Burroughs</li>

<li>the <a href="P-code_machine#Example_machine" title="P-code machine">Niklaus Wirth p-code machine</a></li>

<li><a href="Smalltalk" title="Smalltalk">Smalltalk</a></li>

<li>the <a href="Java_virtual_machine" title="Java virtual machine">Java virtual machine</a> instruction set (note that only the abstract instruction set is stack based, HotSpot, the Sun Java Virtual Machine for instance, does not implement the actual interpreter in software, but as handwritten assembly stubs)</li>

<li>the <a href="WebAssembly" title="WebAssembly">WebAssembly</a> bytecode</li>

<li>the <a href="Virtual_Execution_System" title="Virtual Execution System">Virtual Execution System</a> (VES) for the <a href="Common_Intermediate_Language" title="Common Intermediate Language">Common Intermediate Language</a> (CIL) instruction set of the <a href=".NET_Framework" title=".NET Framework">.NET Framework</a> (ECMA 335)</li>

<li>the <a href="Forth_(programming_language)" title="Forth (programming language)">Forth</a> programming language, especially the integral virtual machine</li>

<li>Adobe's <a href="PostScript" title="PostScript">PostScript</a></li>

<li><a href="Sun_Microsystems" title="Sun Microsystems">Sun Microsystems</a>' SwapDrop programming language for <a href="Sun_Ray" title="Sun Ray">Sun Ray</a> <a href="Smartcard" class="mw-redirect" title="Smartcard">smartcard</a> identification</li>

<li>Adobe's <a href="ActionScript" title="ActionScript">ActionScript</a> Virtual Machine 2 (AVM2)</li>

<li><a href="Ethereum" title="Ethereum">Ethereum</a>'s EVM</li>

<li>the <a href="CPython" title="CPython">CPython</a> <a href="Bytecode" title="Bytecode">bytecode</a> interpreter</li>

<li>the <a href="Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a> <a href="YARV" title="YARV">YARV</a> bytecode interpreter</li>

<li>the <a href="Rubinius" title="Rubinius">Rubinius</a> virtual machine</li>

<li>the <a href="Bs_(programming_language)" title="Bs (programming language)">bs (programming language)</a> in <a href="Unix" title="Unix">Unix</a> uses a virtual stack machine to process commands, after first transposing provided input language form, into reverse-polish notation</li>

<li>the <a href="Dc_(computer_program)" title="Dc (computer program)">dc (computer program)</a> one of the oldest <a href="Unix" title="Unix">Unix</a> programs</li>

<li>the <a href="Lua_(programming_language)" class="mw-redirect" title="Lua (programming language)">Lua (programming language)</a> C API</li>

<li>the TON Virtual Machine (TVM) for <a href="The_Open_Network" class="mw-redirect" title="The Open Network">The Open Network</a> smart contracts</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Hybrid_machines">Hybrid machines</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Hybrid_computer" title="Hybrid computer">hybrid computers</a> that combine both digital and analogue features.</div>

Pure stack machines are quite inefficient for procedures which access multiple fields from the same object. The stack machine code must reload the object pointer for each pointer+offset calculation. A common fix for this is to add some register-machine features to the stack machine: a visible register file dedicated to holding addresses, and register-style instructions for doing loads and simple address calculations. It is uncommon to have the registers be fully general purpose, because then there is no strong reason to have an expression stack and postfix instructions.

Another common hybrid is to start with a register machine architecture, and add another memory address mode which emulates the push or pop operations of stack machines: 'memaddress = reg; reg += instr.displ'. This was first used in <a href="Digital_Equipment_Corporation" title="Digital Equipment Corporation">DEC</a>'s <a href="PDP-11" title="PDP-11">PDP-11</a> minicomputer.<a href="#cite_note-Duncan_1977-22">[22]</a> This feature was carried forward in <a href="VAX" title="VAX">VAX</a> computers and in <a href="Motorola_6809" title="Motorola 6809">Motorola 6809</a> and <a href="Motorola_68000" title="Motorola 68000">M68000</a> microprocessors. This allowed the use of simpler stack methods in early compilers. It also efficiently supported virtual machines using stack interpreters or <a href="Threaded_code" title="Threaded code">threaded code</a>. However, this feature did not help the register machine's own code to become as compact as pure stack machine code. Also, the execution speed was less than when compiling well to the register architecture. It is faster to change the top-of-stack pointer only occasionally (once per call or return) rather than constantly stepping it up and down throughout each program statement, and it is even faster to avoid memory references entirely.

More recently, so-called second-generation stack machines have adopted a dedicated collection of registers to serve as address registers, off-loading the task of memory addressing from the data stack. For example, MuP21 relies on a register called "A", while the more recent GreenArrays processors relies on two registers: A and B.<a href="#cite_note-Colorforth_F18A-23">[23]</a>

The Intel x86 family of microprocessors have a register-style (accumulator) instruction set for most operations, but use stack instructions for its <a href="X87" title="X87">x87</a>, <a href="Intel_8087" title="Intel 8087">Intel 8087</a> floating point arithmetic, dating back to the iAPX87 (8087) coprocessor for the 8086 and 8088. That is, there are no programmer-accessible floating point registers, but only an 80-bit wide, 8-level deep stack. The x87 relies heavily on the x86 CPU for assistance in performing its operations.

<div class="mw-heading mw-heading3"><h3 id="Computers_using_call_stacks_and_stack_frames">Computers using call stacks and stack frames</h3></div>

Most current computers (of any instruction set style) and most compilers use a large <a href="Call_stack" title="Call stack">call-return stack</a> in memory to organize the short-lived local variables and return links for all currently active procedures or functions. Each nested call creates a new stack frame in memory, which persists until that call completes. This call-return stack may be entirely managed by the hardware via specialized address registers and special address modes in the instructions. Or it may be merely a set of conventions followed by the compilers, using generic registers and register+offset address modes. Or it may be something in between.

Since this technique is now nearly universal, even on register machines, it is not helpful to refer to all these machines as stack machines. That term is commonly reserved for machines which also use an expression stack and stack-only arithmetic instructions to evaluate the pieces of a single statement.

Computers commonly provide direct, efficient access to the program's <a href="Global_variable" title="Global variable">global variables</a> and to the local variables of only the current innermost procedure or function, the topmost stack frame. 'Up level' addressing of the contents of callers' stack frames is usually not needed and not supported as directly by the hardware. If needed, compilers support this by passing in frame pointers as additional, hidden parameters.

Some Burroughs stack machines do support up-level refs directly in the hardware, with specialized address modes and a special 'display' register file holding the frame addresses of all outer scopes. Currently, only MCST <a href="Elbrus_(computer)" title="Elbrus (computer)">Elbrus</a> has done this in hardware. When <a href="Niklaus_Wirth" title="Niklaus Wirth">Niklaus Wirth</a> developed the first <a href="Pascal_(programming_language)" title="Pascal (programming language)">Pascal</a> compiler for the <a href="CDC_6000_series" title="CDC 6000 series">CDC 6000</a>, he found that it was faster overall to pass in the frame pointers as a chain, rather than constantly updating complete arrays of frame pointers. This software method also adds no overhead for common languages like C which lack up-level refs.

The same Burroughs machines also supported nesting of tasks or threads. The task and its creator share the stack frames that existed at the time of task creation, but not the creator's subsequent frames nor the task's own frames. This was supported by a <a href="Parent_pointer_tree" title="Parent pointer tree">cactus stack</a>, whose layout diagram resembled the trunk and arms of a <a href="Saguaro" title="Saguaro">Saguaro</a> cactus. Each task had its own memory segment holding its stack and the frames that it owns. The base of this stack is linked to the middle of its creator's stack. In machines with a conventional flat address space, the creator stack and task stacks would be separate heap objects in one heap.

In some programming languages, the outer-scope data environments are not always nested in time. These languages organize their procedure 'activation records' as separate heap objects rather than as stack frames appended to a linear stack.

In simple languages like <a href="Forth_(programming_language)" title="Forth (programming language)">Forth</a> that lack local variables and naming of parameters, stack frames would contain nothing more than return branch addresses and frame management overhead. So their return stack holds bare return addresses rather than frames. The return stack is separate from the data value stack, to improve the flow of call setup and returns.

<div class="mw-heading mw-heading2"><h2 id="Comparison_with_register_machines">Comparison with register machines</h2></div>

Stack machines are often compared to register machines, which hold values in an array of <a href="Processor_register" title="Processor register">registers</a>. Register machines may store stack-like structures in this array, but a register machine has instructions which circumvent the stack interface. Register machines routinely outperform stack machines,<a href="#cite_note-Shi-Gregg-Beatty-Ertl_2005-24">[24]</a> and stack machines have remained a niche player in hardware systems. But stack machines are often used in implementing <a href="Virtual_machine" title="Virtual machine">virtual machines</a> because of their simplicity and ease of implementation.<a href="#cite_note-Randall_2004-25">[25]</a>

<div class="mw-heading mw-heading3"><h3 id="Instructions">Instructions</h3></div>

Stack machines have higher <a href="Instruction_set_architecture#Code_density" title="Instruction set architecture">code density</a>. In contrast to common stack machine instructions which can easily fit in 6 bits or less, register machines require two or three register-number fields per ALU instruction to select operands; the densest register machines average about 16 bits per instruction plus the operands. Register machines also use a wider offset field for load-store opcodes. A stack machine's compact code naturally fits more instructions in cache, and therefore could achieve better <a href="CPU_cache" title="CPU cache">cache</a> efficiency, reducing memory costs or permitting faster memory systems for a given cost. In addition, most stack-machine instructions are very simple, made from only one opcode field or one operand field. Thus, stack-machines require very little electronic resources to decode each instruction.

A program has to execute more instructions when compiled to a stack machine than when compiled to a register machine or memory-to-memory machine. Every variable load or constant requires its own separate Load instruction, instead of being bundled within the instruction which uses that value. The separated instructions may be simple and faster running, but the total instruction count is still higher.

Most register interpreters specify their registers by number. But a host machine's registers can't be accessed in an indexed array, so a memory array is allotted for virtual registers. Therefore, the instructions of a register interpreter must use memory for passing generated data to the next instruction. This forces register interpreters to be much slower on microprocessors made with a fine process rule (i.e. faster transistors without improving circuit speeds, such as the Haswell x86). These require several clocks for memory access, but only one clock for register access. In the case of a stack machine with a data forwarding circuit instead of a register file, stack interpreters can allot the host machine's registers for the top several operands of the stack instead of the host machine's memory

In a stack machine, the operands used in the instructions are always at a known offset (set in the stack pointer), from a fixed location (the bottom of the stack, which in a hardware design might always be at memory location zero), saving precious in-<a href="Cache_(computing)" title="Cache (computing)">cache</a> or in-<a href="CPU" class="mw-redirect" title="CPU">CPU</a> storage from being used to store quite so many <a href="Memory_address" title="Memory address">memory addresses</a> or index numbers. This may preserve such registers and cache for use in non-flow computation.

<div class="mw-heading mw-heading3"><h3 id="Temporary_/_local_values">Temporary / local values</h3></div>

Some in the industry believe that stack machines execute more <a href="Data_cache" class="mw-redirect" title="Data cache">data cache</a> cycles for temporary values and local variables than do register machines.<a href="#cite_note-Hennessy-Patterson-26">[26]</a>

On stack machines, temporary values often get spilled into memory, whereas on machines with many registers these temps usually remain in registers. (However, these values often need to be spilled into "activation frames" at the end of a procedure's definition, basic block, or at the very least, into a memory buffer during interrupt processing). Values spilled to memory add more cache cycles. This spilling effect depends on the number of hidden registers used to buffer top-of-stack values, upon the frequency of nested procedure calls, and upon host computer interrupt processing rates.

On register machines using optimizing compilers, it is very common for the most-used local variables to remain in registers rather than in stack frame memory cells. This eliminates most data cache cycles for reading and writing those values. The development of "stack scheduling" for performing <a href="Live-variable_analysis" title="Live-variable analysis">live-variable analysis</a>, and thus retaining key variables on the stack for extended periods, helps this concern.<a href="#cite_note-Koopman_1994-3">[3]</a><a href="#cite_note-Bailey_2000-4">[4]</a><a href="#cite_note-Shannon-Bailey_2006-5">[5]</a>

On the other hand, register machines must spill many of their registers to memory across nested procedure calls. The decision of which registers to spill, and when, is made statically at compile time rather than on the dynamic depth of the calls. This can lead to more data cache traffic than in an advanced stack machine implementation.

<div class="mw-heading mw-heading3"><h3 id="Common_subexpressions">Common subexpressions</h3></div>

In register machines, a <a href="Common_subexpression" class="mw-redirect" title="Common subexpression">common subexpression</a> (a subexpression which is used multiple times with the same result value) can be evaluated just once and its result saved in a fast register. The subsequent reuses have no time or code cost, just a register reference. This optimization speeds simple expressions (for example, loading variable X or pointer P) as well as less-common complex expressions.

With stack machines, in contrast, results can be stored in one of two ways. Firstly, results can be stored using a temporary variable in memory. Storing and subsequent retrievals cost additional instructions and additional data cache cycles. Doing this is only a win if the subexpression computation costs more in time than fetching from memory, which in most stack CPUs, almost always is the case. It is never worthwhile for simple variables and pointer fetches, because those already have the same cost of one data cache cycle per access. It is only marginally worthwhile for expressions such as <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">X+1</code>. These simpler expressions make up the majority of redundant, optimizable expressions in programs written in languages other than <a href="Concatenative_programming_language" title="Concatenative programming language">concatenative languages</a>. An optimizing compiler can only win on redundancies that the programmer could have avoided in the source code.

The second way leaves a computed value on the data stack, duplicating it as needed. This uses operations to copy stack entries. The stack must be depth shallow enough for the CPU's available copy instructions. Hand-written stack code often uses this approach, and achieves speeds like general-purpose register machines.<a href="#cite_note-Koopman_1989-27">[27]</a><a href="#cite_note-LaForest_2007-9">[9]</a> Unfortunately, algorithms for optimal "stack scheduling" are not in wide use by programming languages.

<div class="mw-heading mw-heading3"><h3 id="Pipelining">Pipelining</h3></div>

In modern machines, the time to fetch a variable from the data cache is often several times longer than the time needed for basic ALU operations. A program runs faster without stalls if its memory loads can be started several cycles before the instruction that needs that variable. Complex machines can do this with a deep pipeline and "out-of-order execution" that examines and runs many instructions at once. Register machines can even do this with much simpler "in-order" hardware, a shallow pipeline, and slightly smarter compilers. The load step becomes a separate instruction, and that instruction is statically scheduled much earlier in the code sequence. The compiler puts independent steps in between.

Scheduling memory accesses requires explicit, spare registers. It is not possible on stack machines without exposing some aspect of the micro-architecture to the programmer. For the expression A B -, B must be evaluated and pushed immediately prior to the Minus step. Without stack permutation or hardware multithreading, relatively little useful code can be put in between while waiting for the Load B to finish. Stack machines can work around the memory delay by either having a deep out-of-order execution pipeline covering many instructions at once, or more likely, they can permute the stack such that they can work on other workloads while the load completes, or they can interlace the execution of different program threads, as in the Unisys A9 system.<a href="#cite_note-Burroughs_1986-28">[28]</a> Today's increasingly parallel computational loads suggests, however, this might not be the disadvantage it's been made out to be in the past.

Stack machines can omit the operand fetching stage of a register machine.<a href="#cite_note-Koopman_1989-27">[27]</a> For example, in the <a href="Java_Optimized_Processor" title="Java Optimized Processor">Java Optimized Processor</a> (JOP) microprocessor the top 2 operands of stack directly enter a data forwarding circuit that is faster than the register file.<a href="#cite_note-Jopdesign-29">[29]</a>

<div class="mw-heading mw-heading3"><h3 id="Out-of-order_execution">Out-of-order execution</h3></div>

The <a href="Tomasulo_algorithm" class="mw-redirect" title="Tomasulo algorithm">Tomasulo algorithm</a> finds <a href="Instruction-level_parallelism" title="Instruction-level parallelism">instruction-level parallelism</a> by issuing instructions as their data becomes available. Conceptually, the addresses of positions in a stack are no different than the register indexes of a register file. This view permits the <a href="Out-of-order_execution" title="Out-of-order execution">out-of-order execution</a> of the Tomasulo algorithm to be used with stack machines.

Out-of-order execution in stack machines seems to reduce or avoid many theoretical and practical difficulties.<a href="#cite_note-Chatterji-Ravindran-30">[30]</a> The cited research shows that such a stack machine can exploit instruction-level parallelism, and the resulting hardware must cache data for the instructions. Such machines effectively bypass most memory accesses to the stack. The result achieves throughput (instructions per <a href="Clock_rate" title="Clock rate">clock</a>) comparable to <a href="Load%E2%80%93store_architecture" title="Load–store architecture">load–store architecture</a> machines, with much higher code densities (because operand addresses are implicit).

One issue brought up in the research was that it takes about 1.88 stack-machine instructions to do the work of one instruction on a load-store architecture machine. Competitive out-of-order stack machines therefore require about twice as many electronic resources to track instructions ("issue stations"). This might be compensated by savings in instruction cache and memory and instruction decoding circuits.

<div class="mw-heading mw-heading3"><h3 id="Hides_a_faster_register_machine_inside">Hides a faster register machine inside</h3></div>

Some simple stack machines have a chip design which is fully customized all the way down to the level of individual registers. The top of stack address register and the N top of stack data buffers are built from separate individual register circuits, with separate adders and ad hoc connections.

However, most stack machines are built from larger circuit components where the N data buffers are stored together within a register file and share read/write buses. The decoded stack instructions are mapped into one or more sequential actions on that hidden register file. Loads and ALU ops act on a few topmost registers, and implicit spills and fills act on the bottommost registers. The decoder allows the instruction stream to be compact. But if the code stream instead had explicit register-select fields which directly manipulated the underlying register file, the compiler could make better use of all registers and the program would run faster.

<a href="Microcode" title="Microcode">Microprogrammed</a> stack machines are an example of this. The inner microcode engine is some kind of RISC-like register machine or a <a href="VLIW" class="mw-redirect" title="VLIW">VLIW</a>-like machine using multiple register files. When controlled directly by task-specific microcode, that engine gets much more work completed per cycle than when controlled indirectly by equivalent stack code for that same task.

The object code translators for the <a href="HP_3000" title="HP 3000">HP 3000</a> and <a href="Tandem_Computers" title="Tandem Computers">Tandem</a> T/16 are another example.<a href="#cite_note-Bergh-Keilman-Magenheimer-Miller_1987-31">[31]</a><a href="#cite_note-Andrews-Sand_1992-32">[32]</a> They translated stack code sequences into equivalent sequences of RISC code. Minor 'local' optimizations removed much of the overhead of a stack architecture. Spare registers were used to factor out repeated address calculations. The translated code still retained plenty of emulation overhead from the mismatch between original and target machines. Despite that burden, the cycle efficiency of the translated code matched the cycle efficiency of the original stack code. And when the source code was recompiled directly to the register machine via optimizing compilers, the efficiency doubled. This shows that the stack architecture and its non-optimizing compilers were wasting over half of the power of the underlying hardware.

Register files are good tools for computing because they have high bandwidth and very low latency, compared to memory references via data caches. In a simple machine, the register file allows reading two independent registers and writing of a third, all in one ALU cycle with one-cycle or less latency. Whereas the corresponding data cache can start only one read or one write (not both) per cycle, and the read typically has a latency of two ALU cycles. That's one third of the throughput at twice the pipeline delay. In a complex machine like <a href="Athlon" title="Athlon">Athlon</a> that completes two or more instructions per cycle, the register file allows reading of four or more independent registers and writing of two others, all in one ALU cycle with one-cycle latency. Whereas the corresponding dual-ported data cache can start only two reads or writes per cycle, with multiple cycles of latency. Again, that's one third of the throughput of registers. It is very expensive to build a cache with additional ports.

Since a stack is a component of most software programs, even when the software used is not strictly a stack machine, a hardware stack machine might more closely mimic the inner workings of its programs. Processor registers have a high thermal cost, and a stack machine might claim higher energy efficiency.<a href="#cite_note-GreenArrays_1-33">[33]</a>

<div class="mw-heading mw-heading3"><h3 id="Interrupts">Interrupts</h3></div>

Responding to an interrupt involves saving the registers to a stack, and then branching to the interrupt handler code. Often stack machines respond more quickly to interrupts, because most parameters are already on a stack and there is no need to push them there. Some register machines deal with this by having multiple register files that can be instantly swapped<a href="#cite_note-Intel_1980-34">[34]</a> but this increases costs and slows down the register file.

<div class="mw-heading mw-heading3"><h3 id="Interpreters">Interpreters</h3></div>

Interpreters for virtual stack machines are easier to build than interpreters for register machines; the logic for handling memory address modes is in just one place rather than repeated in many instructions. Stack machines also tend to have fewer variations of an opcode; one generalized opcode will handle both frequent cases and obscure corner cases of memory references or function call setup. (But code density is often improved by adding short and long forms for the same operation.)

Interpreters for virtual stack machines are often slower than interpreters for other styles of virtual machine.<a href="#cite_note-Shi-Gregg-Beatty-Ertle_2-35">[35]</a> This slowdown is worst when running on host machines with deep execution pipelines, such as current x86 chips.

In some interpreters, the interpreter must execute a N-way switch jump to decode the next opcode and branch to its steps for that particular opcode. Another method for selecting opcodes is <a href="Threaded_code" title="Threaded code">threaded code</a>. The host machine's prefetch mechanisms are unable to predict and fetch the target of that indexed or indirect jump. So the host machine's execution pipeline must restart each time the hosted interpreter decodes another virtual instruction. This happens more often for virtual stack machines than for other styles of virtual machine.<a href="#cite_note-Davis-Beatty-Casey-Gregg-Waldron_2005-36">[36]</a>

One example is the <a href="Java_(programming_language)" title="Java (programming language)">Java</a> programming language.

Its canonical <a href="Virtual_machine" title="Virtual machine">virtual machine</a> is specified as an 8-bit stack machine. However, the <a href="Dalvik_(software)" title="Dalvik (software)">Dalvik</a> virtual machine for Java used on <a href="Android_(operating_system)" title="Android (operating system)">Android</a> <a href="Smartphones" class="mw-redirect" title="Smartphones">smartphones</a> is a 16-bit virtual-register machine - a choice made for efficiency reasons. Arithmetic instructions directly fetch or store local variables via 4-bit (or larger) instruction fields.<a href="#cite_note-Bornstein_2008-37">[37]</a> Similarly version 5.0 of Lua replaced its virtual stack machine with a faster virtual register machine.<a href="#cite_note-Lua5-38">[38]</a><a href="#cite_note-Lua5_VM-39">[39]</a>

Since Java virtual machine became popular, microprocessors have employed advanced <a href="Branch_predictor" title="Branch predictor">branch predictors</a> for indirect jumps.<a href="#cite_note-inria-40">[40]</a> This advance avoids most of pipeline restarts from N-way jumps and eliminates much of the instruction count costs that affect stack interpreters.

<ul><li><a href="Stack-oriented_programming_language" class="mw-redirect" title="Stack-oriented programming language">Stack-oriented programming language</a></li>

<li><a href="Concatenative_programming_language" title="Concatenative programming language">Concatenative programming language</a></li>

<li><a href="Comparison_of_application_virtual_machines" class="mw-redirect" title="Comparison of application virtual machines">Comparison of application virtual machines</a></li>

<li><a href="SECD_machine" title="SECD machine">SECD machine</a></li>

<li><a href="Accumulator_machine" class="mw-redirect" title="Accumulator machine">Accumulator machine</a></li>

<li><a href="Belt_machine" class="mw-redirect" title="Belt machine">Belt machine</a></li>

<li><a href="Random-access_machine" title="Random-access machine">Random-access machine</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBeard1997" class="citation magazine cs1">Beard, Bob (Autumn 1997). <a rel="nofollow" class="external text" href="http://www.cs.man.ac.uk/CCS/res/res18.htm#c">"The KDF9 Computer - 30 Years On"</a>. Computer RESURRECTION.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFHayes1978" class="citation book cs1">Hayes, John P. (1978). Computer Architecture and Organization. McGraw-Hill International Book Company. p. 164. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-07-027363-4</bdi>.</cite>

</li>

<li id="cite_note-Koopman_1994-3">^ <a href="#cite_ref-Koopman_1994_3-0">a</a> <a href="#cite_ref-Koopman_1994_3-1">b</a> <cite id="CITEREFKoopman,_Jr.1994" class="citation journal cs1">Koopman, Jr., Philip John (1994). <a rel="nofollow" class="external text" href="http://www.ece.cmu.edu/~koopman/stack_compiler/stack_co.pdf">"A Preliminary Exploration of Optimized Stack Code Generation"</a> (PDF). Journal of Forth Applications and Research. 6 (3).</cite>

</li>

<li id="cite_note-Bailey_2000-4">^ <a href="#cite_ref-Bailey_2000_4-0">a</a> <a href="#cite_ref-Bailey_2000_4-1">b</a> <cite id="CITEREFBailey2000" class="citation conference cs1">Bailey, Chris (2000). <a rel="nofollow" class="external text" href="http://www.complang.tuwien.ac.at/anton/euroforth/ef00/bailey00.pdf">"Inter-Boundary Scheduling of Stack Operands: A preliminary Study"</a> (PDF). Proceedings of Euroforth 2000 Conference.</cite>

</li>

<li id="cite_note-Shannon-Bailey_2006-5">^ <a href="#cite_ref-Shannon-Bailey_2006_5-0">a</a> <a href="#cite_ref-Shannon-Bailey_2006_5-1">b</a> <cite id="CITEREFShannonBailey2006" class="citation conference cs1">Shannon, Mark; Bailey, Chris (2006). <a rel="nofollow" class="external text" href="http://www.complang.tuwien.ac.at/anton/euroforth2006/papers/shannon.pdf">"Global Stack Allocation: Register Allocation for Stack Machines"</a> (PDF). Proceedings of Euroforth Conference 2006.</cite>

</li>

<li id="cite_note-Barton_1961-6"><a href="#cite_ref-Barton_1961_6-0">^</a> <cite id="CITEREFBarton1961" class="citation conference cs1"><a href="Robert_S._Barton" title="Robert S. Barton">Barton, Robert S.</a> (1961-05-09). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/1460690.1460736">"A new approach to the functional design of a digital computer"</a>. Papers Presented at the 9–11 May 1961, Western Joint IRE-AIEE-ACM Computer Conference. 1961 Western Joint IRE-AIEE-ACM Computer Conference. pp. 393–396. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1460690.1460736">10.1145/1460690.1460736</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-45037872-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29044652">29044652</a>.</cite> <code class="cs1-code">{{cite conference}}</code>: ISBN / Date incompatibility (help)

</li>

<li id="cite_note-Barton_1987-7"><a href="#cite_ref-Barton_1987_7-0">^</a> <cite id="CITEREFBarton1987" class="citation journal cs1"><a href="Robert_S._Barton" title="Robert S. Barton">Barton, Robert S.</a> (1987). <a rel="nofollow" class="external text" href="http://doi.ieeecomputersociety.org/10.1109/MAHC.1987.10002">"A new approach to the functional design of a digital computer"</a>. IEEE Annals of the History of Computing. 9: 11–15. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FMAHC.1987.10002">10.1109/MAHC.1987.10002</a>.</cite>

</li>

<li id="cite_note-Blaauw-Brooks_1997-8"><a href="#cite_ref-Blaauw-Brooks_1997_8-0">^</a> <cite id="CITEREFBlaauwBrooks,_Jr.1997" class="citation book cs1"><a href="Gerrit_Anne_Blaauw" class="mw-redirect" title="Gerrit Anne Blaauw">Blaauw, Gerrit Anne</a>; <a href="Frederick_Phillips_Brooks" class="mw-redirect" title="Frederick Phillips Brooks">Brooks, Jr., Frederick Phillips</a> (1997). Computer architecture: Concepts and evolution. Boston, Massachusetts, USA: <a href="Addison-Wesley_Longman_Publishing_Co.%2C_Inc." class="mw-redirect" title="Addison-Wesley Longman Publishing Co., Inc.">Addison-Wesley Longman Publishing Co., Inc.</a></cite>

</li>

<li id="cite_note-LaForest_2007-9">^ <a href="#cite_ref-LaForest_2007_9-0">a</a> <a href="#cite_ref-LaForest_2007_9-1">b</a> <cite id="CITEREFLaForest2007" class="citation book cs1">LaForest, Charles Eric (April 2007). "2.1 Lukasiewicz and the First Generation: 2.1.2 Germany: Konrad Zuse (1910–1995); 2.2 The First Generation of Stack Computers: 2.2.1 Zuse Z4". <a rel="nofollow" class="external text" href="http://fpgacpu.ca/publications/Second-Generation_Stack_Computer_Architecture.pdf">Second-Generation Stack Computer Architecture</a> (PDF) (thesis). Waterloo, Canada: <a href="University_of_Waterloo" title="University of Waterloo">University of Waterloo</a>. p. 8, 11, etc. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220120155616/http://fpgacpu.ca/publications/Second-Generation_Stack_Computer_Architecture.pdf">Archived</a> (PDF) from the original on 2022-01-20. Retrieved 2022-07-02.</cite> (178 pages) <a rel="nofollow" class="external autonumber" href="https://web.archive.org/web/20110718112702/http://www.eecg.utoronto.ca/~laforest/Second-Generation_Stack_Computer_Architecture.pdf">[1]</a>

</li>

<li id="cite_note-Greve-Wilding_1998-10"><a href="#cite_ref-Greve-Wilding_1998_10-0">^</a> <cite id="CITEREFGreveWilding1998" class="citation journal cs1">Greve, David A.; Wilding, Matthew M. (1998-01-12). <a rel="nofollow" class="external text" href="http://hokiepokie.org/docs/EETimes.ps">"The World's First Java Processor"</a>. Electronic Engineering Times.</cite>

</li>

<li id="cite_note-Xerox_Mesa-11"><a href="#cite_ref-Xerox_Mesa_11-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20240514165724/https://digibarn.com/friends/alanfreier/princops/00yTableOfContents.html">"Mesa Processor Principles of Operation"</a>. DigiBarn Computer Museum. Xerox. Archived from <a rel="nofollow" class="external text" href="https://digibarn.com/friends/alanfreier/princops/00yTableOfContents.html">the original</a> on 2024-05-14. Retrieved 2023-09-20.</cite>

</li>

<li id="cite_note-DigiBarn_Star-12"><a href="#cite_ref-DigiBarn_Star_12-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20240503063200/https://digibarn.com/collections/systems/xerox-8010/index.html">"DigiBarn: The Xerox Star 8010 "Dandelion""</a>. DigiBarn Computer Museum. Archived from <a rel="nofollow" class="external text" href="https://digibarn.com/collections/systems/xerox-8010/index.html">the original</a> on 2024-05-03. Retrieved 2023-09-20.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite class="citation journal cs1"><a rel="nofollow" class="external text" href="https://archive.org/details/Hewlett-Packard_Journal_Vol._34_No._8_1983-08_Hewlett-Packard/page/n9/mode/1up">"Instruction Set for a Single-Chip 32-Bit Processor"</a>. Hewlett-Packard Journal. 34 (8). Hewlett-Packard. August 1983. Retrieved 2024-02-05.</cite>

</li>

<li id="cite_note-MARC4-14"><a href="#cite_ref-MARC4_14-0">^</a> <cite class="citation book cs1"><a rel="nofollow" class="external text" href="https://en.wikichip.org/w/images/4/44/MARC4_4-bit_Microcontrollers_Programmer%27s_Guide.pdf">MARC4 4-bit Microcontrollers Programmer's Guide</a> (PDF). <a href="Atmel" title="Atmel">Atmel</a>.</cite>

</li>

<li id="cite_note-Colorforth-15"><a href="#cite_ref-Colorforth_15-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060215200605/http://www.colorforth.com/chips.html">"Forth chips"</a>. Colorforth.com. Archived from <a rel="nofollow" class="external text" href="http://www.colorforth.com/chips.html">the original</a> on 2006-02-15. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-UT_F21-16"><a href="#cite_ref-UT_F21_16-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.ultratechnology.com/f21.html">"F21 Microprocessor Overview"</a>. Ultratechnology.com. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-ForthHub_2017-17"><a href="#cite_ref-ForthHub_2017_17-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/ForthHub/ForthFreak">"ForthFreak wiki"</a>. GitHub.com. 2017-08-25. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-Java_1999-18"><a href="#cite_ref-Java_1999_18-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.developer.com/guides/a-java-chip-available-now/">"A Java chip available -- now!"</a>. Developer.com. 1999-04-08. Retrieved 2022-07-07.</cite>

</li>

<li id="cite_note-Lundqvist_1995-19"><a href="#cite_ref-Lundqvist_1995_19-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110820085702/http://lundqvist.dyndns.org/Publications/thesis95/ThorGCC.pdf">"Porting the GNU C Compiler to the Thor Microprocessor"</a> (PDF). 1995-12-04. Archived from <a rel="nofollow" class="external text" href="http://lundqvist.dyndns.org/Publications/thesis95/ThorGCC.pdf">the original</a> (PDF) on 2011-08-20. Retrieved 2011-03-30.</cite>

</li>

<li id="cite_note-ZPU-20"><a href="#cite_ref-ZPU_20-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://opencores.org/project,zpu">"ZPU - the world's smallest 32-bit CPU with a GCC tool-chain: Overview"</a>. opencores.org. Retrieved 2015-02-07.</cite>

</li>

<li id="cite_note-Randell-Russell_1964-21"><a href="#cite_ref-Randell-Russell_1964_21-0">^</a> <cite id="CITEREFRandellRussell1964" class="citation book cs1"><a href="Brian_Randell" title="Brian Randell">Randell, Brian</a>; Russell, Lawford John (1964). <a rel="nofollow" class="external text" href="http://www.softwarepreservation.org/projects/ALGOL/book/Randell_ALGOL_60_Implementation_1964.pdf">Algol 60 Implementation</a> (PDF). London, UK: <a href="Academic_Press" title="Academic Press">Academic Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-578150-4</bdi>.</cite> <code class="cs1-code">{{cite book}}</code>: ISBN / Date incompatibility (help)

</li>

<li id="cite_note-Duncan_1977-22"><a href="#cite_ref-Duncan_1977_22-0">^</a> <cite id="CITEREFDuncan1977" class="citation magazine cs1">Duncan, Fraser George (1977-05-01). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20231015112418/https://csdl-downloads.ieeecomputer.org/mags/co/1977/05/01646485.pdf?Expires=1697369097&Policy=eyJTdGF0ZW1lbnQiOlt7IlJlc291cmNlIjoiaHR0cHM6Ly9jc2RsLWRvd25sb2Fkcy5pZWVlY29tcHV0ZXIub3JnL21hZ3MvY28vMTk3Ny8wNS8wMTY0NjQ4NS5wZGYiLCJDb25kaXRpb24iOnsiRGF0ZUxlc3NUaGFuIjp7IkFXUzpFcG9jaFRpbWUiOjE2OTczNjkwOTd9fX1dfQ__&Signature=xUP0yvim4Anf0nWqRYKhw7EINRBgqttNgyV0fOBmg4jGQU~Uo1eP91Mw2CL34gK18qbzYjWRKwqifo7aVUL2hgxz~ZplAiqNXRqbLpbB4bYfoPiJNJ3x0AJmfERxcIG058YoTI8~uiEhmUNgjJkrfSMbqHwUoqit~4p7xFLfFBqiPau56WqdEngihf8OXuDeUxkMvCPgo2tGnN5GCoGY9-ALYc99IxqY8-ltGpsyauyASyerp42tY7E6r7T~6x75q8mjilSfo~tTpJMTdX2DpGepaobjf9D7MAXWv7iko038yLn8Kp8WxQceX6VX8fM85pPPYapXGK4HrPNnUIGeiw__&Key-Pair-Id=K12PMWTCQBDMDT">"Stack Machine Development: Australia, Great Britain, and Europe"</a> (PDF). <a href="Computer_(magazine)" title="Computer (magazine)">Computer</a>. Vol. 10, no. 5. University of Bristol, Bristol, Virginia, USA. pp. 50–52. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FMC.1977.315873">10.1109/MC.1977.315873</a>. <a href="EISSN_(identifier)" class="mw-redirect" title="EISSN (identifier)">eISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1558-0814">1558-0814</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0018-9162">0018-9162</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17013010">17013010</a>. <a href="CODEN_(identifier)" class="mw-redirect" title="CODEN (identifier)">CODEN</a> <a rel="nofollow" class="external text" href="https://cassi.cas.org/searching.jsp?searchIn=codens&exactMatch=y&c=WIy460-R_DY&searchFor=CPTRB4">CPTRB4</a>. Archived from <a rel="nofollow" class="external text" href="https://csdl-downloads.ieeecomputer.org/mags/co/1977/05/01646485.pdf?Expires=1697369097&Policy=eyJTdGF0ZW1lbnQiOlt7IlJlc291cmNlIjoiaHR0cHM6Ly9jc2RsLWRvd25sb2Fkcy5pZWVlY29tcHV0ZXIub3JnL21hZ3MvY28vMTk3Ny8wNS8wMTY0NjQ4NS5wZGYiLCJDb25kaXRpb24iOnsiRGF0ZUxlc3NUaGFuIjp7IkFXUzpFcG9jaFRpbWUiOjE2OTczNjkwOTd9fX1dfQ__&Signature=xUP0yvim4Anf0nWqRYKhw7EINRBgqttNgyV0fOBmg4jGQU~Uo1eP91Mw2CL34gK18qbzYjWRKwqifo7aVUL2hgxz~ZplAiqNXRqbLpbB4bYfoPiJNJ3x0AJmfERxcIG058YoTI8~uiEhmUNgjJkrfSMbqHwUoqit~4p7xFLfFBqiPau56WqdEngihf8OXuDeUxkMvCPgo2tGnN5GCoGY9-ALYc99IxqY8-ltGpsyauyASyerp42tY7E6r7T~6x75q8mjilSfo~tTpJMTdX2DpGepaobjf9D7MAXWv7iko038yLn8Kp8WxQceX6VX8fM85pPPYapXGK4HrPNnUIGeiw__&Key-Pair-Id=K12PMWTCQBDMDT">the original</a> (PDF) on 2023-10-15. Retrieved 2023-10-15.</cite> (3 pages)

</li>

<li id="cite_note-Colorforth_F18A-23"><a href="#cite_ref-Colorforth_F18A_23-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160310112802/http://colorforth.com/inst.htm">"colorForth Instructions"</a>. Colorforth.com. Archived from <a rel="nofollow" class="external text" href="http://www.colorforth.com/inst.htm">the original</a> on 2016-03-10. Retrieved 2017-10-08.</cite> (Instruction set of the F18A cores, named colorForth for historical reasons.)

</li>

<li id="cite_note-Shi-Gregg-Beatty-Ertl_2005-24"><a href="#cite_ref-Shi-Gregg-Beatty-Ertl_2005_24-0">^</a> <cite id="CITEREFShiGreggBeattyErtl2005" class="citation conference cs1">Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertl, M. Anton (2005). "Virtual machine showdown: Stack versus registers". Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments. pp. 153–163. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1064979.1065001">10.1145/1064979.1065001</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1595930477</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:811512">811512</a>.</cite>

</li>

<li id="cite_note-Randall_2004-25"><a href="#cite_ref-Randall_2004_25-0">^</a> <cite id="CITEREFHyde2004" class="citation book cs1"><a href="Randall_Hyde" title="Randall Hyde">Hyde, Randall</a> (2004). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=mM58oD4LATUC&dq=stack%20machines%20simplicity&pg=PA391">Write Great Code, Vol. 2: Thinking Low-Level, Writing High-Level</a>. Vol. 2. <a href="No_Starch_Press" title="No Starch Press">No Starch Press</a>. p. 391. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-59327-065-0</bdi>. Retrieved 2021-06-30.</cite>

</li>

<li id="cite_note-Hennessy-Patterson-26"><a href="#cite_ref-Hennessy-Patterson_26-0">^</a> "Computer Architecture: A Quantitative Approach", <a href="John_L._Hennessy" title="John L. Hennessy">John L. Hennessy</a>, <a href="David_Andrew_Patterson" class="mw-redirect" title="David Andrew Patterson">David Andrew Patterson</a>; See the discussion of stack machines.

</li>

<li id="cite_note-Koopman_1989-27">^ <a href="#cite_ref-Koopman_1989_27-0">a</a> <a href="#cite_ref-Koopman_1989_27-1">b</a> <cite id="CITEREFKoopman,_Jr." class="citation web cs1">Koopman, Jr., Philip John. <a rel="nofollow" class="external text" href="http://www.ece.cmu.edu/~koopman/stack_computers/">"Stack Computers: the new wave"</a>. Ece.cmu.edu. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-Burroughs_1986-28"><a href="#cite_ref-Burroughs_1986_28-0">^</a> <cite class="citation book cs1"><a rel="nofollow" class="external text" href="http://www.bitsavers.org/pdf/burroughs/LargeSystems/A-Series/MCP_3.6/1170057_Introduction_to_A_Series_Systems_3.6_Apr86.pdf">Introduction to A Series Systems</a> (PDF). <a href="Burroughs_Corporation" title="Burroughs Corporation">Burroughs Corporation</a>. April 1986. Retrieved 2023-09-20.</cite>

</li>

<li id="cite_note-Jopdesign-29"><a href="#cite_ref-Jopdesign_29-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.jopdesign.com/doc/stack.pdf">"Design and Implementation of an Efficient Stack Machine"</a> (PDF). Jopdesign.com. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-Chatterji-Ravindran-30"><a href="#cite_ref-Chatterji-Ravindran_30-0">^</a> <cite id="CITEREFSinhaChatterjiRavindran" class="citation web cs1">Sinha, Steve; Chatterji, Satrajit; Ravindran, Kaushik. <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/228556746">"BOOST: Berkeley's Out of Order Stack Thingy"</a>. Research Gate. Retrieved 2023-11-11.</cite>

</li>

<li id="cite_note-Bergh-Keilman-Magenheimer-Miller_1987-31"><a href="#cite_ref-Bergh-Keilman-Magenheimer-Miller_1987_31-0">^</a> <cite id="CITEREFBerghKeilmanMagenheimerMiller1987" class="citation journal cs1">Bergh, Arndt; Keilman, Keith; Magenheimer, Daniel; Miller, James (December 1987). <a rel="nofollow" class="external text" href="https://www.hpl.hp.com/hpjournal/pdfs/IssuePDFs/1987-12.pdf">"HP3000 Emulation on HP Precision Architecture Computers"</a> (PDF). <a href="Hewlett-Packard_Journal" title="Hewlett-Packard Journal">Hewlett-Packard Journal</a>. <a href="Hewlett-Packard" title="Hewlett-Packard">Hewlett-Packard</a>: 87–89. Retrieved 2023-09-20.</cite>

</li>

<li id="cite_note-Andrews-Sand_1992-32"><a href="#cite_ref-Andrews-Sand_1992_32-0">^</a> <cite id="CITEREFKristy_AndrewsDuane_Sand1992" class="citation conference cs1">Kristy Andrews; Duane Sand (October 1992). "Migrating a CISC Computer Family onto RISC via Object Code Translation". Proceedings of ASPLOS-V.</cite>

</li>

<li id="cite_note-GreenArrays_1-33"><a href="#cite_ref-GreenArrays_1_33-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.greenarraychips.com/home/documents/index.php#F18A">"Documents"</a>. GreenArrays, Inc. F18A Technology. Retrieved 2022-07-07.</cite>

</li>

<li id="cite_note-Intel_1980-34"><a href="#cite_ref-Intel_1980_34-0">^</a> 8051 CPU Manual, Intel, 1980

</li>

<li id="cite_note-Shi-Gregg-Beatty-Ertle_2-35"><a href="#cite_ref-Shi-Gregg-Beatty-Ertle_2_35-0">^</a> <cite id="CITEREFShiGreggBeattyErtle" class="citation web cs1">Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertle, M. Anton. <a rel="nofollow" class="external text" href="http://usenix.org/events/vee05/full_papers/p153-yunhe.pdf">"Virtual Machine Showdown: Stack vs. Register Machine"</a> (PDF). Usenix.org. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-Davis-Beatty-Casey-Gregg-Waldron_2005-36"><a href="#cite_ref-Davis-Beatty-Casey-Gregg-Waldron_2005_36-0">^</a> <cite id="CITEREFDavisBeattyCaseyGregg" class="citation web cs1">Davis, Brian; Beatty, Andrew; Casey, Kevin; Gregg, David; Waldron, John. <a rel="nofollow" class="external text" href="https://www.scss.tcd.ie/David.Gregg/papers/Gregg-SoCP-2005.pdf">"The Case for Virtual Register Machines"</a> (PDF). Scss.tcd.ie. Retrieved 2023-09-20.</cite>

</li>

<li id="cite_note-Bornstein_2008-37"><a href="#cite_ref-Bornstein_2008_37-0">^</a> <cite id="CITEREFBornstein2008" class="citation web cs1">Bornstein, Dan (2008-05-29). <a rel="nofollow" class="external text" href="https://sites.google.com/site/io/dalvik-vm-internals/2008-05-29-Presentation-Of-Dalvik-VM-Internals.pdf?attredirects=0">"Presentation of Dalvik VM Internals"</a> (PDF). p. 22. Retrieved 2010-08-16.</cite>

</li>

<li id="cite_note-Lua5-38"><a href="#cite_ref-Lua5_38-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.lua.org/doc/jucs05.pdf">"The Implementation of Lua 5.0"</a> (PDF). Lua.org. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-Lua5_VM-39"><a href="#cite_ref-Lua5_VM_39-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.inf.puc-rio.br/~roberto/talks/lua-ll3.pdf">"The Virtual Machine of Lua 5.0"</a> (PDF). Inf.puc-rio.br. Retrieved 2017-10-08.</cite>

</li>

<li id="cite_note-inria-40"><a href="#cite_ref-inria_40-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://inria.hal.science/hal-01100647/document">"Branch Prediction and the Performance of Interpreters - Don't Trust Folklore"</a>. Hal.inria.fr. Retrieved 2023-09-20.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.excamera.com/sphinx/fpga-j1.html">Homebrew CPU in an FPGA</a> — homebrew stack machine using FPGA</li>

<li><a rel="nofollow" class="external text" href="http://www.holmea.demon.co.uk/Mk1/Architecture.htm">Mark 1 FORTH Computer</a> — homebrew stack machine using discrete logical circuits</li>

<li><a rel="nofollow" class="external text" href="http://www.holmea.demon.co.uk/Mk2/Architecture.htm">Mark 2 FORTH Computer</a> — homebrew stack machine using bitslice/PLD</li>

<li><a rel="nofollow" class="external text" href="http://fpgacpu.ca/stack/Second-Generation_Stack_Computer_Architecture.pdf">Second-Generation Stack Computer Architecture</a> — Thesis about the history and design of stack machines.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-28" href="https://en.wikipedia.org/wiki/?title=Stack_machine&oldid=1292737385">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>